The present invention relates to the field of programmable devices, and the systems and methods for programming the same. Programmable devices, such as FPGAs, typically includes thousands of programmable logic cells that use combinations of logic gates and/or look-up tables to perform a logic operation. Programmable devices also include a number of functional blocks having specialized logic devices adapted to specific logic operations, such as adders, multiply and accumulate circuits, phase-locked loops, and memory. The logic cells and functional blocks are interconnected with a configurable switching circuit. The configurable switching circuit selectively routes connections between the logic cells and functional blocks. By configuring the combination of logic cells, functional blocks, and the switching circuit, a programmable device can be adapted to perform virtually any type of information processing function.
A typical compilation process for determining the configuration of a programmable device, referred to compilation, starts with an extraction phase, followed by a logic synthesis phase, a technology mapping phase, a fitting phase, and an assembly phase. The extraction phase takes a user design, typically expressed as a netlist in a hardware description language such as Verilog or VHDL, and produces a set of logic gates implementing the user design. In the logic synthesis phase, operators such as multiplexers, decoders, adders, and other circuit elements are transformed into logic gates or logic cells. The logic synthesis phase also minimizes the set of logic gates or logic cells to meet design goals such as area or resource usage, operating speed, or power consumption. In the technology mapping phase, the set of logic gates is permuted over the hardware architecture of the programmable device in order to match elements of the user design with corresponding portions of the programmable device. The fitting phase assigns the various portions of the user design to specific logic cells and functional blocks (sometimes referred to as placement) and determines the configuration of the configurable switching circuit used to route signals between these logic cells and functional blocks (sometimes referred to as routing), taking care to satisfy the user timing constraints as much as possible. In the assembly phase, a configuration file defining the programmable device configuration implementing the user design is created. The programmable device configuration can then be loaded into a programmable device to implement the user design. Programmable devices can be configured with the configuration during or after manufacturing.
Finite state machines, commonly referred to as state machines, are widely used in user designs for a variety of purposes, including controlling sequences of actions. A state machine is a model of behavior comprising states and transitions. A state represents the sequence of inputs to the state machine from its start to the present moment. A transition specifies a change in state from the current state, often, though not necessarily, as a result of one or more inputs received. In hardware, state machines are typically implemented as registers to store state variables and combinatorial logic gates to implement transitions and state machine outputs.
Many hardware description languages enable designers to specify state machines directly as a set of states and transitions, rather than as registers, combinatorial logic gates, and connecting wires. The compilation process, often in the extraction and synthesis phases, then converts the state machine description into a corresponding set of registers, combinatorial logic, and connecting wires. Because the states of the state machine are explicitly defined, the compilation software only has to create combinatorial logic and registers corresponding the defined states. As a result, the compilation process typically produces efficient hardware implementations of state machines.
Unfortunately, state machines are sometimes not recognized by the compilation software. This can occur when designers choose to specify the state machine as registers and combinatorial logic gates or when the state machine is not specified in a required format. When the compilation software does not recognize the state machine, it does not know which states are explicitly defined for the state machine and which states are undefined and will never be used. As a result, it must assume that all possible combinations of register values representing states may be used by the circuit, and the resulting hardware implementation is typically much less efficient.
It is therefore desirable for a system and method to identify state machines from the registers and combinatorial logic in user designs and automatically generate a state machine specification. It is further desirable for the system and method to enable optimizations of the hardware implementation of state machines identified in the user design.